//搜索算法
#ifndef __SEARCH__HPP
#define __SEARCH__HPP

#include<iostream>
#include<utility>
#include<math.h>
#include<cstring>
#include"Sort.hpp"
using std::pair;
using std::make_pair;

#define SearchResult pair<bool, NormalType>
#define FindIt(i) make_pair(true, i)
#define MissIt make_pair(false, 0)

namespace NgSiuKei {

#define NormalType unsigned long long

//线性搜索
template<class TheClass>
SearchResult linearSearch(TheClass *array, NormalType len, TheClass val) {
    if(nullptr == array || 0 == len) {
        return MissIt;
    }
    for(NormalType i=0; i<len; ++i) {
        if(val == array[i]) {
            return FindIt(i);
        }
    }
    return MissIt;
}

//哨兵线性搜索
template<class TheClass>
SearchResult sentinelLinearSearch(TheClass *array, NormalType len, TheClass val) {
    if(nullptr == array || 0 == len) {
        return MissIt;
    }
    TheClass lastVal = array[len-1];
    array[len-1] = val;
    NormalType i = 0;
    while(val != array[i]) {
        ++i;
    }
    array[len-1] = lastVal;
    if(i < len-1 || val == lastVal) {
            return FindIt(i);
    }
    return MissIt;
}

//二分搜索
template<class TheClass>
SearchResult binarySearch(TheClass *array, NormalType len, TheClass val) {
    if(nullptr == array || 0 == len) {
        return MissIt;
    }
    quickSort(array, len);
    NormalType left=0, right=len-1, mid;
    while(left <= right) {
        mid = (left+right)/2;
        if(val == array[mid]) {
            return FindIt(mid);
        }
        else if(val < array[mid]) {
            right = mid-1;
        }
        else {
            left = mid+1;
        }
    }
    return MissIt;
}

//元二分搜索
template<class TheClass>
SearchResult oneSidedBinarySearch(TheClass *array, NormalType len, TheClass val) {
    if(nullptr == array || 0 == len) {
        return MissIt;
    }
    quickSort(array, len);
    NormalType lg = 0;
    while((1<<lg) < len-1) {
        ++lg;
    }
    NormalType pos = 0, newPos;
    for(NormalType i=lg; i>=0 && i<=lg; --i) {
        if(val == array[pos]) {
            return FindIt(pos);
        }
        newPos = pos | (1 << i);
        if(newPos < len && array[newPos] <= val) {
            pos = newPos;
        }
    }
    if(val == array[pos]) {
        return FindIt(pos);
    }
    return MissIt;
}

//三元搜索
template<class TheClass>
SearchResult ternarySearch(TheClass (*f)(TheClass), TheClass l, TheClass r) {
    if(nullptr == f || l >= r) {
        return MissIt;
    }
    TheClass m1, m2;
    while(r-l >= 1e-8) {
        m1 = l+(r-l)/3;
        m2 = r-(r-l)/3;
        if(f(m1) <= f(m2)) {//找最小值
            r = m2;
        }
        else {
            l = m1;
        }
    }
    return FindIt(l);
}

//跳跃搜索
template<class TheClass>
SearchResult jumpSearch(TheClass *array, NormalType len, TheClass val) {
    if(nullptr == array || 0 == len) {
        return MissIt;
    }
    quickSort(array, len);
    NormalType jumpDistance = sqrt(len), jumpTime = 0;
    while(array[jumpTime*jumpDistance] <= val) {
        ++jumpTime;
    }
    for(NormalType i=(jumpTime-1)*jumpDistance; i<jumpTime*jumpDistance; ++i) {
        if(val == array[i]) {
            return FindIt(i);
        }
    }
    return MissIt;
}

//插值搜索
template<class TheClass>
SearchResult interpolationSearch(TheClass *array, NormalType len, TheClass val) {
    if(nullptr == array || 0 == len) {
        return MissIt;
    }
    if(1 == len) {
        return ((val == array[0])?(FindIt(0)):(MissIt));
    }
    quickSort(array, len);
    // ---检查是否均匀分布
    TheClass margin = array[1]-array[0];
    if(0 == margin) {
        return ((val == array[0])?(FindIt(0)):(MissIt));
    }
    for(NormalType i=2; i<len; ++i) {
        if(margin != array[i]-array[i-1]) {
            return MissIt;
        }
    }
    //--------end
    NormalType l = 0, r = len-1, mid;
    while(l<r) {
        mid = l + ((val-array[l])/(array[r]-array[l]))*(r-l);
        if(val == array[mid]) {
            return FindIt(mid);
        }
        else if(val < array[mid]) {
            r = mid-1;
        }
        else {
            l = mid+1;
        }
    }
    if(l == r && val == array[l]) {
        return FindIt(l);
    }
    return MissIt;
}

//指数搜索
template<class TheClass>
SearchResult exponentialSearch(TheClass *array, NormalType len, TheClass val) {
    if(nullptr == array || 0 == len) {
        return MissIt;
    }
    quickSort(array, len);
    if(val == array[0]) {
        return FindIt(0);
    }
    NormalType i;
    for(i=1; i<len; i*=2) {
        if(array[i] == val) {
            return FindIt(i);
        }
        else if(array[i] > val) {
            return binarySearch(array+i/2, i/2, val);
        }
    }
    return binarySearch(array+i/2, len-i/2, val);
}

//斐波那契搜索
template<class TheClass>
SearchResult fibonacciSearch(TheClass *array, NormalType len, TheClass val) {
    if(nullptr == array || 0 == len) {
        return MissIt;
    }
    quickSort(array, len);
    if(val == array[0]) {
        return FindIt(0);
    }
    NormalType i;
    NormalType fibonacciIndex;
    NormalType fibonaccis[len];
    fibonaccis[0] = 0;
    fibonaccis[1] = 1;
    for(i=2; i<len; ++i) {
        fibonaccis[i] = fibonaccis[i-1] + fibonaccis[i-2];
        if(fibonaccis[i]>=len) {
            fibonacciIndex = i;
            break;
        }
    }
    TheClass tempArray[fibonaccis[fibonacciIndex]];
    for(i=0; i<len; ++i) {
        tempArray[i] = array[i];
    }
    while(i<fibonaccis[fibonacciIndex]) {
        tempArray[i++] = tempArray[len-1];
    }
    NormalType left = 0, right = len-1, mid;
    while(left <= right && left < len && right < len) {
        if(fibonacciIndex >= len) {
            return MissIt;
        }
        mid = left + fibonaccis[fibonacciIndex-1] - 1;
        if(val == tempArray[mid]) {
            if(mid < len) {
                return FindIt(mid);
            }
            else {
                return FindIt(len-1);
            }
        }
        else if(val < tempArray[mid]) {
            right = mid - 1;
            fibonacciIndex -= 1;
        }
        else {
            left = mid + 1;
            fibonacciIndex -= 2;
        }
    }
    return MissIt;
}

}

#endif